package com.gitee.wsl.collections.queue

import kotlin.test.Test

class PriorityQueueTest {
    @Test
    fun testBase(){
        val priorityQueue = PriorityQueue<String>()
        priorityQueue.offer("1")
        priorityQueue.offer("5")
        priorityQueue.offer("3")
        priorityQueue.offer("7")
        priorityQueue.offer("9")

        println(priorityQueue)

        priorityQueue.poll()

        println(priorityQueue)

        var a = priorityQueue.pollOrNull()
        while ( a != null ){
            print("$a ")
            a = priorityQueue.pollOrNull()
        }
    }

    /**
     *运行结果
    * 10
    * 0
    * 8
    * 2
    * 0
    * 优先级队列已经为空!!!
     */
    @Test
    fun TestPriorityQueue() {
        val arr = intArrayOf(4, 1, 9, 2, 8, 0, 7, 3, 6, 5)

        //默认创建的是小根堆
        // 一般在创建优先级队列对象时，如果知道元素个数，建议就直接将底层容量给好
        // 否则在插入时需要不多的扩容
        // 扩容机制：开辟更大的空间，拷贝元素，这样效率会比较低
        val q = PriorityQueue(arr)
//        val q = PriorityQueue(arr.size)
//        for (e in arr) {
//            q.offer(e)
//        }
        println(q.size.toString() + ":" +  q) // 打印优先级队列中有效元素个数
        println(q.peek()) // 获取优先级最高的元素

        // 从优先级队列中删除两个元素之和，再次获取优先级最高的元素
        q.poll()
        q.poll()
        println(q.size.toString() + ":" +  q) // 打印优先级队列中有效元素个数
        println(q.peek()) // 获取优先级最高的元素
        q.offer(0)
        println(q.peek()) // 获取优先级最高的元素

        // 将优先级队列中的有效元素删除掉，检测其是否为空
        q.clear()
        if (q.isEmpty()) {
            println("优先级队列已经为空!!!")
        } else {
            println("优先级队列不为空")
        }
    }
}